﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace YJKGridTopologyCal.Utilities
{
	public sealed class AlternativePriorityQueue<TPriority, TData> : IEnumerable<PriorityQueueNode<TPriority, TData>>, IEnumerable
	{
		public AlternativePriorityQueue() : this(4)
		{
		}

		public AlternativePriorityQueue(int capacity) : this(capacity, null)
		{
		}

		public AlternativePriorityQueue(IComparer<TPriority> priorityComparer) : this(4, priorityComparer)
		{
		}

		public AlternativePriorityQueue(int capacity, IComparer<TPriority> priorityComparer)
		{
			if (capacity < 1)
			{
				throw new ArgumentOutOfRangeException("capacity", "Capacity must be greater than zero.");
			}
			this.nodes = new List<PriorityQueueNode<TPriority, TData>>(capacity + 1);
			for (int i = 0; i <= capacity; i++)
			{
				this.nodes.Add(null);
			}
			this.Count = 0;
			this.priorityComparer = (priorityComparer ?? Comparer<TPriority>.Default);
		}

		public AlternativePriorityQueue(AlternativePriorityQueue<TPriority, TData> copyFrom)
		{
			if (copyFrom == null)
			{
				throw new System.ArgumentNullException("copyFrom");
			}
			this.nodes = new List<PriorityQueueNode<TPriority, TData>>(copyFrom.nodes.Count);
			this.priorityComparer = copyFrom.priorityComparer;
			for (int i = 0; i < copyFrom.nodes.Count; i++)
			{
				PriorityQueueNode<TPriority, TData> priorityQueueNode = copyFrom.nodes[i];
				PriorityQueueNode<TPriority, TData> item = (priorityQueueNode == null) ? null : new PriorityQueueNode<TPriority, TData>(priorityQueueNode);
				this.nodes.Add(item);
			}
		}

		public int Count { get; private set; }

		public PriorityQueueNode<TPriority, TData> Head
		{
			get
			{
				return this.nodes[1];
			}
		}

		public void Clear()
		{
			this.nodes.Clear();
			this.nodes.Add(null);
			this.nodes.Add(null);
			this.Count = 0;
		}

		public bool Contains(PriorityQueueNode<TPriority, TData> node)
		{
			return node != null && node.QueueIndex < this.nodes.Count && this.nodes[node.QueueIndex] == node;
		}

		public void Enqueue(PriorityQueueNode<TPriority, TData> node, TPriority priority)
		{
			if (node == null)
			{
				throw new System.ArgumentNullException("node");
			}
			node.Priority = priority;
			int num = this.Count + 1;
			this.Count = num;
			node.QueueIndex = num;
			if (this.nodes.Count <= this.Count)
			{
				this.nodes.Add(null);
			}
			this.nodes[this.Count] = node;
			this.HeapifyUp(this.nodes[this.Count]);
		}

		public PriorityQueueNode<TPriority, TData> Dequeue()
		{
			PriorityQueueNode<TPriority, TData> head = this.Head;
			this.Remove(head);
			return head;
		}

		public void ChangePriority(PriorityQueueNode<TPriority, TData> node, TPriority priority)
		{
			if (node == null)
			{
				throw new System.ArgumentNullException("node");
			}
			node.Priority = priority;
			this.OnNodeUpdated(node);
		}

		public bool Remove(PriorityQueueNode<TPriority, TData> node)
		{
			if (!this.Contains(node))
			{
				return false;
			}
			if (this.Count <= 1)
			{
				this.nodes[1] = null;
				this.Count = 0;
				return true;
			}
			bool flag = false;
			PriorityQueueNode<TPriority, TData> priorityQueueNode = this.nodes[this.Count];
			if (node.QueueIndex != this.Count)
			{
				this.Swap(node, priorityQueueNode);
				flag = true;
			}
			int count = this.Count - 1;
			this.Count = count;
			this.nodes[node.QueueIndex] = null;
			if (flag)
			{
				this.OnNodeUpdated(priorityQueueNode);
			}
			return true;
		}

		public IEnumerator<PriorityQueueNode<TPriority, TData>> GetEnumerator()
		{
			return this.nodes.Skip(1).Take(this.Count).GetEnumerator();
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}

		private void HeapifyUp(PriorityQueueNode<TPriority, TData> node)
		{
			for (int i = node.QueueIndex / 2; i >= 1; i = node.QueueIndex / 2)
			{
				PriorityQueueNode<TPriority, TData> priorityQueueNode = this.nodes[i];
				if (this.HasHigherPriority(priorityQueueNode, node))
				{
					break;
				}
				this.Swap(node, priorityQueueNode);
			}
		}

		private void HeapifyDown(PriorityQueueNode<TPriority, TData> node)
		{
			int num = node.QueueIndex;
			for (;;)
			{
				PriorityQueueNode<TPriority, TData> priorityQueueNode = node;
				int num2 = 2 * num;
				if (num2 > this.Count)
				{
					break;
				}
				PriorityQueueNode<TPriority, TData> priorityQueueNode2 = this.nodes[num2];
				if (this.HasHigherPriority(priorityQueueNode2, priorityQueueNode))
				{
					priorityQueueNode = priorityQueueNode2;
				}
				int num3 = num2 + 1;
				if (num3 <= this.Count)
				{
					PriorityQueueNode<TPriority, TData> priorityQueueNode3 = this.nodes[num3];
					if (this.HasHigherPriority(priorityQueueNode3, priorityQueueNode))
					{
						priorityQueueNode = priorityQueueNode3;
					}
				}
				if (priorityQueueNode == node)
				{
					goto IL_94;
				}
				this.nodes[num] = priorityQueueNode;
				int queueIndex = priorityQueueNode.QueueIndex;
				priorityQueueNode.QueueIndex = num;
				num = queueIndex;
			}
			node.QueueIndex = num;
			this.nodes[num] = node;
			return;
			IL_94:
			node.QueueIndex = num;
			this.nodes[num] = node;
		}

		private void OnNodeUpdated(PriorityQueueNode<TPriority, TData> node)
		{
			int num = node.QueueIndex / 2;
			PriorityQueueNode<TPriority, TData> lower = this.nodes[num];
			if (num > 0 && this.HasHigherPriority(node, lower))
			{
				this.HeapifyUp(node);
				return;
			}
			this.HeapifyDown(node);
		}

		private void Swap(PriorityQueueNode<TPriority, TData> node1, PriorityQueueNode<TPriority, TData> node2)
		{
			this.nodes[node1.QueueIndex] = node2;
			this.nodes[node2.QueueIndex] = node1;
			int queueIndex = node1.QueueIndex;
			node1.QueueIndex = node2.QueueIndex;
			node2.QueueIndex = queueIndex;
		}

		private bool HasHigherPriority(PriorityQueueNode<TPriority, TData> higher, PriorityQueueNode<TPriority, TData> lower)
		{
			return this.priorityComparer.Compare(higher.Priority, lower.Priority) < 0;
		}

		private const int DefaultCapacity = 4;

		private readonly List<PriorityQueueNode<TPriority, TData>> nodes;

		private readonly IComparer<TPriority> priorityComparer;
	}
}
